package Offer.offer2019;

/**
 * 旋转数组的最小值
 * 原数组为递增数组
 * 一般情况 {3,4,5,1,2}
 * 特殊情况一 {1,1,1,0,1}或{1,0,1,1,1}
 * 特殊情况二 {1,2,3,4,5}
 *
 * @author: leiwenkang02@meituan.com
 * @date: 2019/4/20
 * @time: 12:01
 */
public class Offer08 {

    public static void main(String[] args) {
        Offer08 offer08 = new Offer08();
//        int[] array = {3, 4, 5, 1, 2};
//        int[] array = {1, 1, 1, 0, 1};
        int[] array = {1, 2, 3, 4, 5};

        int result = offer08.getMinValue(array);
        System.out.println(result);
    }

    public int getMinValue(int[] array) {
        if (array == null || array.length == 0) {
            throw new RuntimeException("输入非法!");
        }
        //一般情况{3,4,5,1,2}，思路是二分查找
        int start = 0;
        int end = array.length - 1;
        int mid = start;
        while (array[start] >= array[end]) {
            if (end - start == 1) {//首尾两个指针相邻，首指针指向5，尾指针指向1，此时尾指针指向为最小值
                mid = end;
                break;
            }
            mid = (start + end) >> 1;
            //特殊情况一： {1,1,1,0,1}或{1,0,1,1,1}
            if (array[start] == array[end] && array[start] == array[mid]) {
                return orderFindMinValue(array, start, end);
            }
            if (array[mid] >= array[start]) {
                start = mid;
            } else if (array[mid] <= array[end]) {
                end = mid;
            }
        }
        //特殊情况二： {1,2,3,4,5} 旋转元素为0 array[start] < array[end]
        return array[mid];
    }

    /**
     * 顺序查找最小值
     *
     * @param array
     * @return
     */
    private int orderFindMinValue(int[] array, int start, int end) {
        int min = array[0];
        for (int i = start; i <= end; i++) {
            if (array[i] < min) {
                min = array[i];
            }
        }
        return min;
    }
}
